package com.arron.algorithm.leetcodetop100.二叉树;

import com.arron.algorithm.tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 114. 二叉树展开为链表
 */
public class Flatten {


    List<TreeNode> res = new ArrayList<>();

    private TreeNode pre = null;

    public void flatten01(TreeNode root) {
        trave(root);
        for (int i = 0; i < res.size(); i++) {
            TreeNode treeNode = res.get(i);
            if (i+1== res.size()){
                treeNode.right=null;
            }else {
                treeNode.right=res.get(i+1);
            }
            treeNode.left=null;
        }
    }

    /**
     * 树的先序遍历
     * @param root
     */
    public void trave(TreeNode root){

        if(root ==null){
            return;
        }
        res.add(root);
        trave(root.left);
        trave(root.right);

    }

    public void flatten02(TreeNode root) {

        trave02(root);
    }

    /**
     * 树的后续遍历的特殊形式
     * @param root
     */
    public void trave02(TreeNode root){

        if(root ==null){
            return;
        }

        trave02(root.right);
        trave02(root.left);
        //这里将右子树的最后一个节点 的右指针指向pre ,pre 不断迭代记录前一个节点指针
        root.right = pre;
        root.left = null;
        pre = root;


    }



}
